package com.origin.niuke.array;

import java.util.ArrayList;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/5/23 20:52
 * 合并区间
 * 算法：贪心
 */
public class NC37 {

    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        intervals.sort((a, b) -> {
            if (a.start != b.start) return a.start - b.start;
            return a.end - b.end;
        });
        int n = intervals.size();
        ArrayList<Interval> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int j = i;
            while (j < n && intervals.get(j).end >= intervals.get(j + 1).start) ++j;
            ans.add(new Interval(intervals.get(i).start, intervals.get(j).end));
            i = j;
        }
        return ans;
    }

    static class Interval {
        int start;
        int end;

        Interval() {
            start = 0;
            end = 0;
        }

        Interval(int s, int e) {
            start = s;
            end = e;
        }
    }

}
